فهرست مطالب
Transactions on Combinatorics
Volume:8 Issue: 1, Mar 2019
- تاریخ انتشار: 1397/12/10
- تعداد عناوین: 5
-
-
Pages 1-14Let $ G = (V,E) $ be a graph. We say that $ S subseteq V $ is a defensive alliance if for every $ u in S $, the number of neighbors $ u $ has in $ S $ plus one (counting $ u $) is at least as large as the number of neighbors it has outside $ S $. Then, for every vertex $ u $ in a defensive alliance $ S $, any attack on a single vertex by the neighbors of $ u $ in $ V-S $ can be thwarted by the neighbors of $ u $ in $ S $ and $ u $ itself. In this paper, we study alliances that are containing a given vertex $ u $ and study their mathematical properties.Keywords: Defensive alliance, Alliances in graphs, Edge cut
-
Pages 15-40Fixed-point-free permutations, also known as derangements, have been studied for centuries. In particular, depending on their applications, derangements of prime-power order and of prime order have always played a crucial role in a variety of different branches of mathematics: from number theory to algebraic graph theory. Substantial progress has been made on the study of derangements, many long-standing open problems have been solved, and many new research problems have arisen. The results obtained and the methods developed in this area have also effectively been used to solve other problems regarding finite vertex-transitive graphs. The methods used in this area range from deep group theory, including the classification of the finite simple groups, to combinatorial techniques. This article is devoted to surveying results, open problems and methods in this area.Keywords: Derangements, Polycirculant Conjecture, Transitive group
-
Pages 41-50In this article we study the Zero forcing number of Generalized Sierpi'{n}ski graphs $S(G,t)$. More precisely, we obtain a general lower bound on the Zero forcing number of $S(G,t)$ and we show that this bound is tight. In particular, we consider the cases in which the base graph $G$ is a star, path, a cycle or a complete graph.Keywords: Zero forcing number, generalized Sierpi', {n}ski graph, Sierpi', {n}ski graph, path covering
-
Pages 51-59A set $D$ of vertices of graph $G$ is called $double$ $dominating$ $set$ if for any vertex $v$, $|N[v]cap D|geq 2$. The minimum cardinality of $double$ $domination$ of $G$ is denoted by $gamma_d(G)$. The minimum number of edges $E'$ such that $gamma_d(Gsetminus E)>gamma_d(G)$ is called the double bondage number of $G$ and is denoted by $b_d(G)$. This paper determines that $b_d(Gvee H)$ and exact values of $b(P_ntimes P_2)$, and generalized corona product of graphs.Keywords: bondage number, double domination, double bondage number
-
Pages 61-68Let $G$ be a graph. A function $f : V (G) longrightarrow {0,1}$, satisfying the condition that every vertex $u$ with $f(u) = 0$ is adjacent with at least one vertex $v$ such that $f(v) = 1$, is called a dominating function $(DF)$. The weight of $f$ is defined as $wet(f)=Sigma_{v in V(G)} f(v)$. The minimum weight of a dominating function of $G$ is denoted by $gamma (G)$, and is called the domination number of $G$. A dominating function $f$ is called a global dominating function $(GDF)$ if $f$ is also a $DF$ of $overline{G}$. The minimum weight of a global dominating function is denoted by $gamma_{g}(G)$ and is called global domination number of $G$. In this paper we introduce a generalization of global dominating function. Suppose $G$ is a graph and $sgeq 2$ and $K_n$ is the complete graph on $V(G)$. A function $ f:V(G)longrightarrow { 0,1} $ on $G$ is $s$-dominating function $(s-DF)$, if there exists some factorization ${G_1,ldots,G_s }$ of $K_n$, such that $G_1=G$ and $f$ is dominating function of each $G_i$.Keywords: dominating function, global dominating function, $s$-dominating function, $gamma-$function, $gamma, s-$function